package main

import (
	"fmt"
	"math"
)

func main() {
	/*
			1
		  /	| \
		2 - 3 - 4
		  \    /
			5

	*/

	n = 5
	//                  1  2  3  4  5
	w[1] = [1000]int{m, 0, 1, 2, 1, m}
	w[2] = [1000]int{m, 1, 0, 2, m, 1}
	w[3] = [1000]int{m, 2, 2, 0, 2, m}
	w[4] = [1000]int{m, 1, m, 2, 0, 1}
	w[5] = [1000]int{m, m, 1, m, 1, 0}
	ans := floyd()
	if ans == m {
		fmt.Println("no min cycle")
	} else {
		fmt.Println(ans)
	}
}

var m = math.MaxInt / 5
var w [1000][1000]int
var n int

func floyd() (ans int) {
	ans = m
	var dis [1000][1000]int
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			dis[i][j] = w[i][j]
		}
	}
	for k := 1; k <= n; k++ {

		//这套循环必须写在前面，才能表示最短路点集还未包含k点，因为还未处理k点嘛，k点处理在下面那一套循环中
		//注意i，k的起始值，这样处理才表示不重复的i，j点集
		for i := 1; i < k; i++ {
			for j := i + 1; j < k; j++ {
				ans = min(ans, dis[i][j]+w[j][k]+w[k][i])
			}
		}
		//TODO: 由此得出一条经天纬地的做事结论：要想把事情最终做成功，必须要有一条经过逻辑验证的正确理论，跟着理论实践才是最终正确的；反之，乱猜瞎蒙最终只能得到一个错误结果！！！

		//这套循环正常处理Floyd最短路，这里就是处理经过k点时的最短路
		for i := 1; i <= n; i++ {
			for j := 1; j <= n; j++ {
				dis[i][j] = min(dis[i][j], w[i][k]+w[k][j])
			}
		}
	}
	return
}
